/**
 * @license Copyright 2020 The Lighthouse Authors. All Rights Reserved.
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0
 * Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
 */
'use strict';

const MainThreadTasks = require('./main-thread-tasks.js');

const SAMPLER_TRACE_EVENT_NAME = 'FunctionCall-SynthesizedByProfilerModel';

/**
 * @fileoverview
 *
 * This model converts the `Profile` and `ProfileChunk` mega trace events from the `disabled-by-default-v8.cpu_profiler`
 * category into B/E-style trace events that main-thread-tasks.js already knows how to parse into a task tree.
 *
 * The V8 CPU profiler measures where time is being spent by sampling the stack (See https://www.jetbrains.com/help/profiler/Profiling_Guidelines__Choosing_the_Right_Profiling_Mode.html
 * for a generic description of the differences between tracing and sampling).
 *
 * A `Profile` event is a record of the stack that was being executed at different sample points in time.
 * It has a structure like this:
 *
 *    nodes: [function A, function B, function C]
 *    samples: [node with id 2, node with id 1, ...]
 *    timeDeltas: [4125μs since last sample, 121μs since last sample, ...]
 *
 * Note that this is subtly different from the protocol-based Crdp.Profiler.Profile type.
 *
 * Helpful prior art:
 * @see https://cs.chromium.org/chromium/src/third_party/devtools-frontend/src/front_end/sdk/CPUProfileDataModel.js?sq=package:chromium&g=0&l=42
 * @see https://github.com/v8/v8/blob/99ca333b0efba3236954b823101315aefeac51ab/tools/profile.js
 * @see https://github.com/jlfwong/speedscope/blob/9ed1eb192cb7e9dac43a5f25bd101af169dc654a/src/import/chrome.ts#L200
 */

/**
 * @typedef CpuProfile
 * @property {string} id
 * @property {number} pid
 * @property {number} tid
 * @property {number} startTime
 * @property {Required<LH.TraceCpuProfile>['nodes']} nodes
 * @property {Array<number>} samples
 * @property {Array<number>} timeDeltas
 */

/** @typedef {Required<Required<LH.TraceEvent['args']>['data']>['_syntheticProfilerRange']} ProfilerRange */
/** @typedef {LH.TraceEvent & {args: {data: {_syntheticProfilerRange: ProfilerRange}}}} SynthethicEvent */
/** @typedef {Omit<LH.Artifacts.TaskNode, 'event'> & {event: SynthethicEvent, endEvent: SynthethicEvent}} SynthethicTaskNode */

class CpuProfilerModel {
  /**
   * @param {CpuProfile} profile
   */
  constructor(profile) {
    this._profile = profile;
    this._nodesById = this._createNodeMap();
    this._activeNodeArraysById = this._createActiveNodeArrays();
  }

  /**
   * Initialization function to enable O(1) access to nodes by node ID.
   * @return {Map<number, CpuProfile['nodes'][0]>}
   */
  _createNodeMap() {
    /** @type {Map<number, CpuProfile['nodes'][0]>} */
    const map = new Map();
    for (const node of this._profile.nodes) {
      map.set(node.id, node);
    }

    return map;
  }

  /**
   * Initialization function to enable O(1) access to the set of active nodes in the stack by node ID.
   * @return {Map<number, Array<number>>}
   */
  _createActiveNodeArrays() {
    /** @type {Map<number, Array<number>>} */
    const map = new Map();
    /** @param {number} id @return {Array<number>} */
    const getActiveNodes = id => {
      if (map.has(id)) return map.get(id) || [];

      const node = this._nodesById.get(id);
      if (!node) throw new Error(`No such node ${id}`);
      if (typeof node.parent === 'number') {
        const array = getActiveNodes(node.parent).concat([id]);
        map.set(id, array);
        return array;
      } else {
        return [id];
      }
    };

    for (const node of this._profile.nodes) {
      map.set(node.id, getActiveNodes(node.id));
    }

    return map;
  }

  /**
   * Returns all the node IDs in a stack when a specific nodeId is at the top of the stack
   * (i.e. a stack's node ID and the node ID of all of its parents).
   *
   * @param {number} nodeId
   * @return {Array<number>}
   */
  _getActiveNodeIds(nodeId) {
    const activeNodeIds = this._activeNodeArraysById.get(nodeId);
    if (!activeNodeIds) throw new Error(`No such node ID ${nodeId}`);
    return activeNodeIds;
  }

  /**
   * Generates the necessary B/E-style trace events for a single transition from stack A to stack B
   * at the given latest timestamp (includes possible range in event.args.data).
   *
   * Example:
   *
   *    latestPossibleTimestamp 1234
   *    previousNodeIds 1,2,3
   *    currentNodeIds 1,2,4
   *
   *    yields [end 3 at ts 1234, begin 4 at ts 1234]
   *
   * @param {number} earliestPossibleTimestamp
   * @param {number} latestPossibleTimestamp
   * @param {Array<number>} previousNodeIds
   * @param {Array<number>} currentNodeIds
   * @return {Array<SynthethicEvent>}
   */
  _synthesizeTraceEventsForTransition(
      earliestPossibleTimestamp,
      latestPossibleTimestamp,
      previousNodeIds,
      currentNodeIds
  ) {
    const startNodes = currentNodeIds
      .filter(id => !previousNodeIds.includes(id))
      .map(id => this._nodesById.get(id))
      .filter(/** @return {node is CpuProfile['nodes'][0]} */ node => !!node);
    const endNodes = previousNodeIds
      .filter(id => !currentNodeIds.includes(id))
      .map(id => this._nodesById.get(id))
      .filter(/** @return {node is CpuProfile['nodes'][0]} */ node => !!node);

    /** @param {CpuProfile['nodes'][0]} node @return {SynthethicEvent} */
    const createSyntheticEvent = node => ({
      ts: Number.isFinite(latestPossibleTimestamp)
        ? latestPossibleTimestamp
        : earliestPossibleTimestamp,
      pid: this._profile.pid,
      tid: this._profile.tid,
      dur: 0,
      ph: 'I',
      // This trace event name is Lighthouse-specific and wouldn't be found in a real trace.
      // Attribution logic in main-thread-tasks.js special cases this event.
      name: SAMPLER_TRACE_EVENT_NAME,
      cat: 'lighthouse',
      args: {
        data: {
          callFrame: node.callFrame,
          _syntheticProfilerRange: {earliestPossibleTimestamp, latestPossibleTimestamp},
        },
      },
    });

    /** @type {Array<SynthethicEvent>} */
    const startEvents = startNodes.map(createSyntheticEvent).map(evt => ({...evt, ph: 'B'}));
    /** @type {Array<SynthethicEvent>} */
    const endEvents = endNodes.map(createSyntheticEvent).map(evt => ({...evt, ph: 'E'}));
    // Ensure we put end events in first to finish prior tasks before starting new ones.
    return [...endEvents.reverse(), ...startEvents];
  }

  /**
   * @param {LH.TraceEvent | undefined} event
   * @return {event is SynthethicEvent}
   */
  static isSyntheticEvent(event) {
    if (!event) return false;
    return Boolean(
      event.name === SAMPLER_TRACE_EVENT_NAME &&
      event.args.data &&
      event.args.data._syntheticProfilerRange
    );
  }

  /**
   * @param {LH.Artifacts.TaskNode} task
   * @return {task is SynthethicTaskNode}
   */
  static isSyntheticTask(task) {
    return CpuProfilerModel.isSyntheticEvent(task.event) &&
      CpuProfilerModel.isSyntheticEvent(task.endEvent);
  }

  /**
   * Finds all the tasks that started or ended (depending on `type`) within the provided time range.
   * Uses a memory index to remember the place in the array the last invocation left off to avoid
   * re-traversing the entire array, but note that this index might still be slightly off from the
   * true start position.
   *
   * @param {Array<{startTime: number, endTime: number}>} knownTasks
   * @param {{type: 'startTime'|'endTime', initialIndex: number, earliestPossibleTimestamp: number, latestPossibleTimestamp: number}} options
   */
  static _getTasksInRange(knownTasks, options) {
    const {type, initialIndex, earliestPossibleTimestamp, latestPossibleTimestamp} = options;

    // We may have overshot a little from last time, so back up to find the real starting index.
    let startIndex = initialIndex;
    while (startIndex > 0) {
      const task = knownTasks[startIndex];
      if (task && task[type] < earliestPossibleTimestamp) break;
      startIndex--;
    }

    /** @type {Array<{startTime: number, endTime: number}>} */
    const matchingTasks = [];
    for (let i = startIndex; i < knownTasks.length; i++) {
      const task = knownTasks[i];
      // Task is before our range of interest, keep looping.
      if (task[type] < earliestPossibleTimestamp) continue;

      // Task is after our range of interest, we're done.
      if (task[type] > latestPossibleTimestamp) {
        return {tasks: matchingTasks, lastIndex: i};
      }

      // Task is in our range of interest, add it to our list.
      matchingTasks.push(task);
    }

    // We went through all tasks before reaching the end of our range.
    return {tasks: matchingTasks, lastIndex: knownTasks.length};
  }

  /**
   * Given a particular time range and a set of known true tasks, find the correct timestamp to use
   * for a transition between tasks.
   *
   * Because the sampling profiler only provides a *range* of start/stop function boundaries, this
   * method uses knowledge of a known set of tasks to find the most accurate timestamp for a particular
   * range. For example, if we know that a function ended between 800ms and 810ms, we can use the
   * knowledge that a toplevel task ended at 807ms to use 807ms as the correct endtime for this function.
   *
   * @param {{syntheticTask: SynthethicTaskNode, eventType: 'start'|'end', allEventsAtTs: {naive: Array<SynthethicEvent>, refined: Array<SynthethicEvent>}, knownTaskStartTimeIndex: number, knownTaskEndTimeIndex: number, knownTasksByStartTime: Array<{startTime: number, endTime: number}>, knownTasksByEndTime: Array<{startTime: number, endTime: number}>}} data
   * @return {{timestamp: number, lastStartTimeIndex: number, lastEndTimeIndex: number}}
   */
  static _findEffectiveTimestamp(data) {
    const {
      eventType,
      syntheticTask,
      allEventsAtTs,
      knownTasksByStartTime,
      knownTaskStartTimeIndex,
      knownTasksByEndTime,
      knownTaskEndTimeIndex,
    } = data;

    const targetEvent = eventType === 'start' ? syntheticTask.event : syntheticTask.endEvent;
    const pairEvent = eventType === 'start' ? syntheticTask.endEvent : syntheticTask.event;

    const timeRange = targetEvent.args.data._syntheticProfilerRange;
    const pairTimeRange = pairEvent.args.data._syntheticProfilerRange;

    const {tasks: knownTasksStarting, lastIndex: lastStartTimeIndex} = this._getTasksInRange(
      knownTasksByStartTime,
      {
        type: 'startTime',
        initialIndex: knownTaskStartTimeIndex,
        earliestPossibleTimestamp: timeRange.earliestPossibleTimestamp,
        latestPossibleTimestamp: timeRange.latestPossibleTimestamp,
      }
    );

    const {tasks: knownTasksEnding, lastIndex: lastEndTimeIndex} = this._getTasksInRange(
      knownTasksByEndTime,
      {
        type: 'endTime',
        initialIndex: knownTaskEndTimeIndex,
        earliestPossibleTimestamp: timeRange.earliestPossibleTimestamp,
        latestPossibleTimestamp: timeRange.latestPossibleTimestamp,
      }
    );

    // First, find all the tasks that span *across* (not fully contained within) our ambiguous range.
    const knownTasksStartingNotContained = knownTasksStarting
      .filter(t => !knownTasksEnding.includes(t));
    const knownTasksEndingNotContained = knownTasksEnding
      .filter(t => !knownTasksStarting.includes(t));

    // Each one of these spanning tasks can be in one of three situations:
    //    - Task is a parent of the sample.
    //    - Task is a child of the sample.
    //    - Task has no overlap with the sample.

    // Parent tasks must satisfy...
    //     parentTask.startTime <= syntheticTask.startTime
    //                         AND
    //     syntheticTask.endTime <= parentTask.endTime
    const parentTasks =
      eventType === 'start'
        ? knownTasksStartingNotContained.filter(
            t => t.endTime >= pairTimeRange.earliestPossibleTimestamp
          )
        : knownTasksEndingNotContained.filter(
            t => t.startTime <= pairTimeRange.latestPossibleTimestamp
          );

    // Child tasks must satisfy...
    //     syntheticTask.startTime <= childTask.startTime
    //                         AND
    //     childTask.endTime <= syntheticTask.endTime
    const childTasks =
      eventType === 'start'
        ? knownTasksStartingNotContained.filter(
            t => t.endTime < pairTimeRange.earliestPossibleTimestamp
          )
        : knownTasksEndingNotContained.filter(
            t => t.startTime > pairTimeRange.latestPossibleTimestamp
          );

    // Unrelated tasks must satisfy...
    //     unrelatedTask.endTime <= syntheticTask.startTime
    //                       OR
    //     syntheticTask.endTime <= unrelatedTask.startTime
    const unrelatedTasks =
          eventType === 'start' ? knownTasksEndingNotContained : knownTasksStartingNotContained;

    // Now we narrow our allowable range using the three types of tasks and the other events
    // that we've already refined.
    const minimumTs = Math.max(
      // Sampled event couldn't be earlier than this to begin with.
      timeRange.earliestPossibleTimestamp,
      // Sampled start event can't be before its parent started.
      // Sampled end event can't be before its child ended.
      ...(eventType === 'start'
        ? parentTasks.map(t => t.startTime)
        : childTasks.map(t => t.endTime)),
      // Sampled start event can't be before unrelated tasks ended.
      ...(eventType === 'start' ? unrelatedTasks.map(t => t.endTime) : []),
      // Sampled start event can't be before the other `E` events at its same timestamp.
      ...(eventType === 'start'
        ? allEventsAtTs.refined.filter(e => e.ph === 'E').map(e => e.ts)
        : [])
    );

    const maximumTs = Math.min(
      // Sampled event couldn't be later than this to begin with.
      timeRange.latestPossibleTimestamp,
      // Sampled start event can't be after its child started.
      // Sampled end event can't be after its parent ended.
      ...(eventType === 'start'
        ? childTasks.map(t => t.startTime)
        : parentTasks.map(t => t.endTime)),
      // Sampled end event can't be after unrelated tasks started.
      ...(eventType === 'start' ? [] : unrelatedTasks.map(t => t.startTime)),
      // Sampled end event can't be after the other `B` events at its same timestamp.
      // This is _currently_ only possible in contrived scenarios due to the sorted order of processing,
      // but it's a non-obvious observation and case to account for.
      ...(eventType === 'start'
        ? []
        : allEventsAtTs.refined.filter(e => e.ph === 'B').map(e => e.ts))
    );

    // We want to maximize the size of the sampling tasks within our constraints, so we'll pick
    // the _earliest_ possible time for start events and the _latest_ possible time for end events.
    const effectiveTimestamp =
      (eventType === 'start' && Number.isFinite(minimumTs)) || !Number.isFinite(maximumTs)
        ? minimumTs
        : maximumTs;

    return {timestamp: effectiveTimestamp, lastStartTimeIndex, lastEndTimeIndex};
  }

  /**
   * Creates the B/E-style trace events using only data from the profile itself. Each B/E event will
   * include the actual _range_ the timestamp could have been in its metadata that is used for
   * refinement later.
   *
   * @return {Array<SynthethicEvent>}
   */
  _synthesizeNaiveTraceEvents() {
    const profile = this._profile;
    const length = profile.samples.length;
    if (profile.timeDeltas.length !== length) throw new Error(`Invalid CPU profile length`);

    /** @type {Array<SynthethicEvent>} */
    const events = [];

    let currentProfilerTimestamp = profile.startTime;
    let earliestPossibleTimestamp = -Infinity;

    /** @type {Array<number>} */
    let lastActiveNodeIds = [];
    for (let i = 0; i < profile.samples.length; i++) {
      const nodeId = profile.samples[i];
      const timeDelta = Math.max(profile.timeDeltas[i], 1);
      const node = this._nodesById.get(nodeId);
      if (!node) throw new Error(`Missing node ${nodeId}`);

      currentProfilerTimestamp += timeDelta;

      const activeNodeIds = this._getActiveNodeIds(nodeId);
      events.push(
        ...this._synthesizeTraceEventsForTransition(
          earliestPossibleTimestamp,
          currentProfilerTimestamp,
          lastActiveNodeIds,
          activeNodeIds
        )
      );

      earliestPossibleTimestamp = currentProfilerTimestamp;
      lastActiveNodeIds = activeNodeIds;
    }

    events.push(
      ...this._synthesizeTraceEventsForTransition(
        currentProfilerTimestamp,
        Infinity,
        lastActiveNodeIds,
        []
      )
    );

    return events;
  }

  /**
   * Creates a copy of B/E-style trace events with refined timestamps using knowledge from the
   * tasks that have definitive timestamps.
   *
   * With the sampling profiler we know that a function started/ended _sometime between_ two points,
   * but not exactly when. Using the information from other tasks gives us more information to be
   * more precise with timings and allows us to create a valid task tree later on.
   *
   * @param {Array<{startTime: number, endTime: number}>} knownTasks
   * @param {Array<SynthethicTaskNode>} syntheticTasks
   * @param {Array<SynthethicEvent>} syntheticEvents
   * @return {Array<SynthethicEvent>}
   */
  _refineTraceEventsWithTasks(knownTasks, syntheticTasks, syntheticEvents) {
    /** @type {Array<SynthethicEvent>} */
    const refinedEvents = [];

    /** @type {Map<number, {naive: Array<SynthethicEvent>, refined: Array<SynthethicEvent>}>} */
    const syntheticEventsByTs = new Map();
    for (const event of syntheticEvents) {
      const group = syntheticEventsByTs.get(event.ts) || {naive: [], refined: []};
      group.naive.push(event);
      syntheticEventsByTs.set(event.ts, group);
    }

    /** @type {Map<SynthethicEvent, SynthethicTaskNode>} */
    const syntheticTasksByEvent = new Map();
    for (const task of syntheticTasks) {
      syntheticTasksByEvent.set(task.event, task);
      syntheticTasksByEvent.set(task.endEvent, task);
    }

    const knownTasksByStartTime = knownTasks.slice().sort((a, b) => a.startTime - b.startTime);
    const knownTasksByEndTime = knownTasks.slice().sort((a, b) => a.endTime - b.endTime);

    let knownTaskStartTimeIndex = 0;
    let knownTaskEndTimeIndex = 0;

    for (const event of syntheticEvents) {
      const syntheticTask = syntheticTasksByEvent.get(event);
      if (!syntheticTask) throw new Error('Impossible - all events have a task');
      const allEventsAtTs = syntheticEventsByTs.get(event.ts);
      if (!allEventsAtTs) throw new Error('Impossible - we just mapped every event');

      const effectiveTimestampData = CpuProfilerModel._findEffectiveTimestamp({
        eventType: event.ph === 'B' ? 'start' : 'end',
        syntheticTask,
        allEventsAtTs,
        knownTaskStartTimeIndex,
        knownTaskEndTimeIndex,
        knownTasksByStartTime,
        knownTasksByEndTime,
      });

      knownTaskStartTimeIndex = effectiveTimestampData.lastStartTimeIndex;
      knownTaskEndTimeIndex = effectiveTimestampData.lastEndTimeIndex;

      const refinedEvent = {...event, ts: effectiveTimestampData.timestamp};
      refinedEvents.push(refinedEvent);
      allEventsAtTs.refined.push(refinedEvent);
    }

    return refinedEvents;
  }

  /**
   * Creates B/E-style trace events from a CpuProfile object created by `collectProfileEvents()`.
   * An optional set of tasks can be passed in to refine the start/end times.
   *
   * @param {Array<LH.Artifacts.TaskNode>} [knownTaskNodes]
   * @return {Array<LH.TraceEvent>}
   */
  synthesizeTraceEvents(knownTaskNodes = []) {
    const naiveEvents = this._synthesizeNaiveTraceEvents();
    if (!naiveEvents.length) return [];

    let finalEvents = naiveEvents;
    if (knownTaskNodes.length) {
      // If we have task information, put the times back into raw trace event ts scale.
      /** @type {(baseTs: number) => (node: LH.Artifacts.TaskNode) => LH.Artifacts.TaskNode} */
      const rebaseTaskTime = baseTs => node => ({
        ...node,
        startTime: baseTs + node.startTime * 1000,
        endTime: baseTs + node.endTime * 1000,
        duration: node.duration * 1000,
      });

      // The first task node might not be time 0, so recompute the baseTs.
      const baseTs = knownTaskNodes[0].event.ts - knownTaskNodes[0].startTime * 1000;
      const knownTasks = knownTaskNodes.map(rebaseTaskTime(baseTs));

      // We'll also create tasks for our naive events so we have the B/E pairs readily available.
      const naiveProfilerTasks = MainThreadTasks.getMainThreadTasks(naiveEvents, [], Infinity)
        .map(rebaseTaskTime(naiveEvents[0].ts))
        .filter(CpuProfilerModel.isSyntheticTask);
      if (!naiveProfilerTasks.length) throw new Error('Failed to create naive profiler tasks');

      finalEvents = this._refineTraceEventsWithTasks(knownTasks, naiveProfilerTasks, naiveEvents);
    }

    return finalEvents;
  }

  /**
   * Creates B/E-style trace events from a CpuProfile object created by `collectProfileEvents()`
   *
   * @param {CpuProfile} profile
   * @param {Array<LH.Artifacts.TaskNode>} tasks
   * @return {Array<LH.TraceEvent>}
   */
  static synthesizeTraceEvents(profile, tasks) {
    const model = new CpuProfilerModel(profile);
    return model.synthesizeTraceEvents(tasks);
  }

  /**
   * Merges the data of all the `ProfileChunk` trace events into a single CpuProfile object for consumption
   * by `synthesizeTraceEvents()`.
   *
   * @param {Array<LH.TraceEvent>} traceEvents
   * @return {Array<CpuProfile>}
   */
  static collectProfileEvents(traceEvents) {
    /** @type {Map<string, CpuProfile>} */
    const profiles = new Map();
    for (const event of traceEvents) {
      if (event.name !== 'Profile' && event.name !== 'ProfileChunk') continue;
      if (typeof event.id !== 'string') continue;

      // `Profile` or `ProfileChunk` can partially define these across multiple events.
      // We'll fallback to empty values and worry about validation in the `synthesizeTraceEvents` phase.
      const cpuProfileArg = (event.args.data && event.args.data.cpuProfile) || {};
      const timeDeltas =
        (event.args.data && event.args.data.timeDeltas) || cpuProfileArg.timeDeltas;
      let profile = profiles.get(event.id);

      if (event.name === 'Profile') {
        profile = {
          id: event.id,
          pid: event.pid,
          tid: event.tid,
          startTime: (event.args.data && event.args.data.startTime) || event.ts,
          nodes: cpuProfileArg.nodes || [],
          samples: cpuProfileArg.samples || [],
          timeDeltas: timeDeltas || [],
        };
      } else {
        if (!profile) continue;
        profile.nodes.push(...(cpuProfileArg.nodes || []));
        profile.samples.push(...(cpuProfileArg.samples || []));
        profile.timeDeltas.push(...(timeDeltas || []));
      }

      profiles.set(profile.id, profile);
    }

    return Array.from(profiles.values());
  }
}

module.exports = CpuProfilerModel;
